This invention relates to the field of data processing; and more particularly, it relates to methods of routing messages through an array of data processing nodes such that multiple paths can be taken to reach a destination without causing message routing deadlocks to occur.
As used herein, the term data processing node is meant to include the combination of at least the following items: a microprocessor chip, a memory coupled to the microprocessor, and input-output channels to and from the microprocessor. Here, the microprocessor/memory/input-output channels can have any internal make-up.
Such a data processing node has use by itself in that the memory can store a program for the microprocessor to execute, and data can be sent to and received from the data processing node via the input-output channels. However, by intercoupling multiple data processing nodes together in an array via their input-output channels, several advantages over a single data processing node are achieved.
One advantage is that an array of nodes provides a selectable or scalable amount of computing power. To increase/decrease the computing power of the array, some nodes are simply added to/deleted from the array.
Also, another advantage is that the array of nodes provides computing power which is fail-soft. This means that one or more nodes can fail and be in need of repair, while the remaining nodes in the array continue to operate.
However, in any array of data processing nodes, an issue that needs to be addressed is how to route information in the form of messages from one node to another node. Such message routing is of course needed in order for the nodes of the array to work on data processing problems in a coordinated and cooperative fashion.
Presently in the art, Intel Corporation sells a scalable parallel processor, called the "Paragon", which comprises an array of data processing nodes that are intercoupled with channels as a "mesh". Within this mesh, the data processing nodes are arranged in rows and columns; and messages are passed from node to node along those rows and columns.
However, a major drawback with the above scalable parallel processor is that the route which each message takes from its source to its destination is fixed. Consequently, whenever the route for a message is blocked because it requires a channel that is busy, that message must wait for the channel to become available. Further, if the route for a message is blocked by a broken channel, that message will not reach its destination until the channel break is fixed.
Accordingly, a primary object of the invention is to provide an improved method of routing messages through an array of data processing nodes whereby the above drawbacks are overcome.